﻿#pragma once
#include <string>
#include <bitset>
#include <vector>
#include "Bitmap.h"

struct BKDRHash {
	size_t operator()(const string& key) {
		size_t hash = 0;
		for (auto e : key) {
			hash *= 31;//为了解决"abc" "acb"结果相同(BKDR)
			hash += e;
		}
		return hash;//返回string中所有字符ASCII码值相加		
	}
};

struct APHash {
	size_t operator()(const string& key) {
		size_t hash = 0;
		for (size_t i = 0; i < key.size(); i++) {
			char ch = key[i];
			if ((i & 1) == 0)
				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
			else
				hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
		}
		return hash;
	}
};

struct DJBHash {
	size_t operator()(const string& key) {
		size_t hash = 5381;
		for (auto ch : key)
			hash += (hash << 5) + ch;
		return hash;
	}
};

template <size_t N, class K = string, class HashFunc1 = BKDRHash, class HashFunc2 = APHash, class HashFunc3 = DJBHash>
class BloomFilter {
public:
	void Set(const K& key) {
		//HashFunc1() 创建了一个该类型的临时匿名对象（调用了默认构造函数）
		//HashFunc1()(key) 对这个临时对象调用了 operator()，并传入 key 作为参数。
		size_t hash1 = HashFunc1()(key) % N;
		size_t hash2 = HashFunc2()(key) % N;
		size_t hash3 = HashFunc3()(key) % N;

		_bs.set(hash1);
		_bs.set(hash2);
		_bs.set(hash3);
	}

	bool Test(const K& key) {
		size_t hash1 = HashFunc1()(key) % N;
		if (_bs.test(hash1) == false) return false;
		size_t hash2 = HashFunc2()(key) % N;
		if (_bs.test(hash2) == false) return false;
		size_t hash3 = HashFunc3()(key) % N;
		if (_bs.test(hash3) == false) return false;

		return true;
	}

	//将数据映射的比特位置为0是不支持的
	//因为不同的数据可能映射到同一个比特位
	//想支持删除要使用引用计数，
	//即有几个数据映射到该位置就显示几，但数据多了一个比特位就不足以支持
	//用多个比特位标记一个值，存引用计数
	void Reset(const K& key);
private:
	bit::bitset<N> _bs;
};

void TestBF1() {
	BloomFilter<100> bf;
	bf.Set("猪八戒");
	bf.Set("沙悟净");
	bf.Set("孙悟空");
	bf.Set("二郎神");

	cout << bf.Test("猪八戒") << endl;
	cout << bf.Test("沙悟净") << endl;
	cout << bf.Test("孙悟空") << endl;
	cout << bf.Test("二郎神") << endl;
	cout << bf.Test("二郎神1") << endl;
	cout << bf.Test("二郎神2") << endl;
	cout << bf.Test("二郎神 ") << endl;
	cout << bf.Test("太白金星") << endl;
}

void TestBF2() {
	srand((size_t)time(0));
	const size_t N = 10000;
	//BloomFilter<N * 4> bf;
	BloomFilter<N * 10> bf;//误判率显著降低

	vector<string> v1;
	string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
	//string url = "猪八戒";

	for (size_t i = 0; i < N; ++i)
		v1.push_back(url + to_string(i));

	for (auto& str : v1)
		bf.Set(str);

	// v2跟v1是相似字符串集（前缀一样），但是不一样
	vector<std::string> v2;
	for (size_t i = 0; i < N; ++i) {
		string urlstr = url;
		urlstr += to_string(9999999 + i);
		v2.push_back(urlstr);
	}

	size_t n2 = 0;
	for (auto& str : v2)
		if (bf.Test(str)) // 误判	
			++n2;


	cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;

	// 不相似字符串集
	vector<string> v3;
	for (size_t i = 0; i < N; ++i) {
		//string url = "zhihu.com";
		string url = "孙悟空";
		url += to_string(i + rand());
		v3.push_back(url);
	}

	size_t n3 = 0;
	for (auto& str : v3)
		if (bf.Test(str))
			++n3;

	cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}